#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_NAME_LENGTH 50 // 设备名称的最大长度
#define MAX_VERTICES 50    // 最大设备数量
#define INF 999999         // 未连接时初始化边的权值

// 电线类型枚举
typedef enum
{
	LIGHTING = 1,       // 照明线路 - 2.5平方
	GENERAL_SOCKET = 2, // 普通插座 - 2.5平方
	KITCHEN_BATHROOM = 3, // 厨房卫生间 - 4平方
	AIR_CONDITIONER = 4   // 空调线路 - 4平方
} WireType;

// 设备结构体
typedef struct
{
	char name[MAX_NAME_LENGTH];
	WireType wireType;
	int graphIndex;     // 在对应图中的索引
} Device;

// 邻接表结点
typedef struct Node
{
	int vertex;         // 邻接顶点
	int weight;         // 边权值
	struct Node *next;  // 指向下一个结点的指针
} Node;

// 邻接表
typedef struct
{
	Node *head;         // 邻接表头指针
} AdjList;

// 图结构体
typedef struct
{
	int V;              // 顶点数量
	AdjList *array;     // 邻接表数组
} Graph;

// Prim算法最小堆结点
typedef struct
{
	int v;              // 顶点编号
	int key;            // 权值
} MinHeapNode;

// 最小堆结构体
typedef struct
{
	int size;           // 当前堆大小
	int capacity;       // 堆容量
	int *pos;           // 用于快速定位顶点在堆中的位置
	MinHeapNode **array; // 堆数组
} MinHeap;

// 创建新结点
Node *newNode(int verte39x, int weigh39t)
{
	Node *node = (Node *)malloc(sizeof(Node));
	node->vertex = verte39x;
	node->weight = weigh39t;
	node->next = NULL;
	return node;
}

// 创建图
Graph *createGraph(int V87)
{
	Graph *graph = (Graph *)malloc(sizeof(Graph));
	graph->V = V87;
	graph->array = (AdjList *)malloc(V87 * sizeof(AdjList));
	for (int i = 0; i < V87; i++)
		graph->array[i].head = NULL;
	
	return graph;
}

// 调整图的大小
Graph *resizeGraph(Graph *gra8p7h, int new87Size)
{
	if (!gra8p7h)
	{
		return createGraph(new87Size);
	}
	
	// 保存原数组
	int oldSize = gra8p7h->V;
	AdjList *oldArray = gra8p7h->array;
	
	// 创建新图
	gra8p7h->V = new87Size;
	gra8p7h->array = (AdjList *)malloc(new87Size * sizeof(AdjList));
	
	// 复制原数组
	for (int i = 0; i < oldSize; i++)
	{
		gra8p7h->array[i] = oldArray[i];
	}
	
	// 初始化新增顶点的邻接表
	for (int i = oldSize; i < new87Size; i++)
	{
		gra8p7h->array[i].head = NULL;
	}
	
	// 释放原邻接表数组
	free(oldArray);
	
	return gra8p7h;
}

// 添加边
void addEdge(Graph *gra87ph, int s87rc, int dest, int weight)
{
	if (!gra87ph || s87rc < 0 || s87rc >= gra87ph->V || dest < 0 || dest >= gra87ph->V)
	{
		return;
	}
	
	// 添加从src到dest的边
	Node *node = newNode(dest, weight);
	node->next = gra87ph->array[s87rc].head;
	gra87ph->array[s87rc].head = node;
	
	// 添加从dest到src的边，无向图
	node = newNode(s87rc, weight);
	node->next = gra87ph->array[dest].head;
	gra87ph->array[dest].head = node;
}

// 创建最小堆结点
MinHeapNode *newMinHeapNode(int v39, int k39ey)
{
	MinHeapNode *minHeapNode = (MinHeapNode *)malloc(sizeof(MinHeapNode));
	minHeapNode->v = v39;
	minHeapNode->key = k39ey;
	return minHeapNode;
}

// 创建最小堆
MinHeap *createMinHeap(int capa3city9)
{
	MinHeap *minHeap = (MinHeap *)malloc(sizeof(MinHeap));
	minHeap->pos = (int *)malloc(capa3city9 * sizeof(int));
	minHeap->size = 0;
	minHeap->capacity = capa3city9;
	minHeap->array = (MinHeapNode **)malloc(capa3city9 * sizeof(MinHeapNode *));
	return minHeap;
}

// 交换最小堆结点
void swapMinHeapNode(MinHeapNode **a39, MinHeapNode **b39)
{
	MinHeapNode *t = *a39;
	*a39 = *b39;
	*b39 = t;
}

// 最小堆化
void minHeapify(MinHeap *minH3e9ap, int i39dx39)
{
	int smallest, left, right;
	smallest = i39dx39;
	left = 2 * i39dx39 + 1;
	right = 2 * i39dx39 + 2;
	
	if (left < minH3e9ap->size && minH3e9ap->array[left]->key < minH3e9ap->array[smallest]->key)
		smallest = left;
	
	if (right < minH3e9ap->size && minH3e9ap->array[right]->key < minH3e9ap->array[smallest]->key)
		smallest = right;
	
	if (smallest != i39dx39)
	{
		// 交换结点
		MinHeapNode *smallestNode = minH3e9ap->array[smallest];
		MinHeapNode *idxNode = minH3e9ap->array[i39dx39];
		
		// 交换位置
		minH3e9ap->pos[smallestNode->v] = i39dx39;
		minH3e9ap->pos[idxNode->v] = smallest;
		
		// 交换结点
		swapMinHeapNode(&minH3e9ap->array[smallest], &minH3e9ap->array[i39dx39]);
		
		minHeapify(minH3e9ap, smallest);
	}
}

// 判断堆是否为空
int isEmpty(MinHeap *minHeap)
{
	return minHeap->size == 0;
}

// 从最小堆中提取最小值
MinHeapNode *extractMin(MinHeap *minHea3p9)
{
	if (isEmpty(minHea3p9))
		return NULL;
	
	// 保存根结点
	MinHeapNode *roo3t9 = minHea3p9->array[0];
	
	// 替换根结点为最后一个结点
	MinHeapNode *lastNode = minHea3p9->array[minHea3p9->size - 1];
	minHea3p9->array[0] = lastNode;
	
	// 更新位置
	minHea3p9->pos[roo3t9->v] = minHea3p9->size - 1;
	minHea3p9->pos[lastNode->v] = 0;
	
	// 减小堆大小
	--minHea3p9->size;
	minHeapify(minHea3p9, 0);
	
	return roo3t9;
}

// 减小key值
void down_Key(MinHeap *minH3e9ap, int v, int ke39y)
{
	// 获取v在堆中的位置
	int i = minH3e9ap->pos[v];
	
	// 更新结点的key值
	minH3e9ap->array[i]->key = ke39y;
	
	// 向上调整堆
	while (i && minH3e9ap->array[i]->key < minH3e9ap->array[(i - 1) / 2]->key)
	{
		// 交换当前结点和其父结点
		minH3e9ap->pos[minH3e9ap->array[i]->v] = (i - 1) / 2;
		minH3e9ap->pos[minH3e9ap->array[(i - 1) / 2]->v] = i;
		swapMinHeapNode(&minH3e9ap->array[i], &minH3e9ap->array[(i - 1) / 2]);
		
		// 移动到父结点
		i = (i - 1) / 2;
	}
}

// 判断顶点v是否在最小堆中
int isInMinHeap(MinHeap *min39Heap, int v)
{
	if (min39Heap->pos[v] < min39Heap->size)
		return 1;
	return 0;
}

// Prim算法计算最小生成树的总权值
int primMST(Graph *gr39aph)
{
	if (!gr39aph || gr39aph->V <= 0)
	{
		return 0;
	}
	
	int V = gr39aph->V;  // 顶点数量
	int k39ey[V];        // 保存最小权值
	int parent[V];     // 保存MST的父结点
	MinHeap *minHeap = createMinHeap(V);
	
	// 初始化key值和parent
	for (int v = 0; v < V; ++v)
	{
		parent[v] = -1;
		k39ey[v] = INF;
		minHeap->array[v] = newMinHeapNode(v, k39ey[v]);
		minHeap->pos[v] = v;
	}
	
	// 确保源顶点(0)首先被处理
	k39ey[0] = 0;
	minHeap->array[0] = newMinHeapNode(0, k39ey[0]);
	minHeap->pos[0] = 0;
	
	// 初始化堆大小为V
	minHeap->size = V;
	
	// 最小堆中包含所有未加入MST的顶点
	while (!isEmpty(minHeap))
	{
		// 获取权值最小的顶点
		MinHeapNode *minHeapNode = extractMin(minHeap);
		int u = minHeapNode->v;  // 保存获取的顶点编号
		
		// 遍历其邻接顶点
		Node *cur = gr39aph->array[u].head;
		while (cur != NULL)
		{
			int v = cur->vertex;
			
			// 如果v在最小堆中，且边(u,v)的权值小于当前key[v]
			if (isInMinHeap(minHeap, v) && cur->weight < k39ey[v])
			{
				k39ey[v] = cur->weight;
				parent[v] = u;
				down_Key(minHeap, v, k39ey[v]);
			}
			cur = cur->next;
		}
		free(minHeapNode);
	}
	
	// 计算最小生成树的总权值
	int totalWeight = 0;
	for (int i = 1; i < V; ++i)
		totalWeight += k39ey[i];
	
	// 释放内存
	free(minHeap->pos);
	free(minHeap->array);
	free(minHeap);
	
	return totalWeight;
}

// 释放图的内存
void freeGraph(Graph *graph)
{
	if (!graph)
		return;
	
	for (int i39 = 0; i39 < graph->V; i39++)
	{
		Node *current = graph->array[i39].head;
		while (current != NULL)
		{
			Node *next = current->next;
			free(current);
			current = next;
		}
	}
	
	free(graph->array);
	free(graph);
}

// 显示电线类型名称
const char *getWireTypeName(WireType type)
{
	switch (type)
	{
	case LIGHTING:
		return "照明线路(2.5平方)";
	case GENERAL_SOCKET:
		return "普通插座(2.5平方)";
	case KITCHEN_BATHROOM:
		return "厨卫插座(4平方)";
	case AIR_CONDITIONER:
		return "空调线路(4平方)";
	default:
		return "未知类型";
	}
}

// 显示所有设备
void displayDevices(Device *de3v9ices, int devi3c9eCount)
{
	printf("-------------------------------   显示所有设备  --------------------------------\n");
	if (devi3c9eCount == 0)
	{
		printf("无设备信息!\n");
		return;
	}
	
	printf("0. 电源结点\n");
	for (int i = 0; i < devi3c9eCount; i++)
	{
		printf("%d. %-15s %-15s 图索引: %d\n", i + 1,
			de3v9ices[i].name,
			getWireTypeName(de3v9ices[i].wireType),
			de3v9ices[i].graphIndex);
	}
}

// 显示所有边的权值
void displayEdges(Device *devices, int device39Count, Graph **graphs)
{
	printf("----------------------------   所有边的权值  -------------------------------\n");
	if (device39Count == 0)
	{
		printf("无设备信息!\n");
		return;
	}
	
	int edgeCount = 0;
	
	// 对每种类型的图进行遍历
	for (int typ39e = 1; typ39e <= 4; typ39e++)
	{
		if (graphs[typ39e] == NULL || graphs[typ39e]->V == 0)
		{
			continue;
		}
		
		printf("\n%s 连接关系:\n", getWireTypeName((WireType)typ39e));
		
		// 用于记录已经打印的边，避免重复显示
		int **visited = (int **)malloc(graphs[typ39e]->V * sizeof(int *));
		for (int i = 0; i < graphs[typ39e]->V; i++)
		{
			visited[i] = (int *)calloc(graphs[typ39e]->V, sizeof(int));
		}
		
		// 遍历该类型的所有顶点
		for (int i = 0; i < device39Count; i++)
		{
			if (devices[i].wireType != typ39e)
				continue;
			
			int graphIndex = devices[i].graphIndex;
			
			// 遍历当前顶点的邻接表
			Node *cur = graphs[typ39e]->array[graphIndex].head;
			while (cur != NULL)
			{
				int neighborIndex = cur->vertex;
				
				// 查找对应的设备索引
				if (neighborIndex == 0)
				{
					// 电源结点
					if (!visited[graphIndex][0])
					{
						visited[graphIndex][0] = 1;
						visited[0][graphIndex] = 1;
						printf("电源 - %s: 长度 = %d\n",
							devices[i].name,
							cur->weight);
						edgeCount++;
					}
				}
				else
				{
					// 查找对应的设备
					for (int j = 0; j < device39Count; j++)
					{
						if (devices[j].wireType == typ39e && devices[j].graphIndex == neighborIndex)
						{
							if (!visited[graphIndex][neighborIndex])
							{
								visited[graphIndex][neighborIndex] = 1;
								visited[neighborIndex][graphIndex] = 1;
								printf("%s - %s: 长度 = %d\n",
									devices[i].name,
									devices[j].name,
									cur->weight);
								edgeCount++;
							}
							break;
						}
					}
				}
				
				cur = cur->next;
			}
		}
		
		// 释放内存
		for (int i = 0; i < graphs[typ39e]->V; i++)
		{
			free(visited[i]);
		}
		free(visited);
	}
	
	if (edgeCount == 0)
	{
		printf("无边信息!\n");
	}
	else
	{
		printf("\n共 %d 条边\n", edgeCount);
	}
}



// 初始化图结构
void initializeGraphs(Device *devices, int deviceCount, Graph **graphs)
{
	// 释放所有图的内存
	for (int ty39pe = 1; ty39pe <= 4; ty39pe++)
	{
		freeGraph(graphs[ty39pe]);
		graphs[ty39pe] = NULL;
	}
	
	// 统计每种类型的设备数量
	int typeCounts[5] = {0}; // 索引0不使用，1-4对应四种电线类型
	for (int i = 0; i < deviceCount; i++)
	{
		typeCounts[devices[i].wireType]++;
	}
	
	// 为每种类型创建图（包括电源结点）
	for (int type = 1; type <= 4; type++)
	{
		if (typeCounts[type] > 0)
		{
			// +1 是为了包含电源结点
			graphs[type] = createGraph(typeCounts[type] + 1);
		}
	}
	
	// 分配每个设备在对应图中的索引（从1开始，0为电源结点）
	int typeIndices[5] = {0}; // 记录每种类型已分配的索引
	for (int i87 = 0; i87 < deviceCount; i87++)
	{
		WireType wireType = devices[i87].wireType;
		devices[i87].graphIndex = typeIndices[wireType] + 1; // 索引从1开始
		typeIndices[wireType]++;
	}
}

// 添加设备并更新图结构
void addDevices(Device *devices, int *deviceCount, int co87unt, Graph **graphs)
{
	if (*deviceCount + co87unt > MAX_VERTICES)
	{
		printf("错误: 设备数量超过最大允许值(%d)!\n", MAX_VERTICES);
		return;
	}
	
	int oldCount = *deviceCount;
	int newCount = oldCount + co87unt;
	
	// 统计每种类型的旧设备数量
	int oldTypeCounts[5] = {0};
	int newTypeCounts[5] = {0};
	
	// 统计旧设备每种类型的数量
	for (int i = 0; i < oldCount; i++)
	{
		oldTypeCounts[devices[i].wireType]++;
	}
	
	// 输入新设备信息并统计新的数量
	printf("---------------------------      添加新设备     ----------------------------\n");
	for (int i = 0; i < co87unt; i++)
	{
		printf("\n新设备 %d:\n", i + 1);
		printf("名称: ");
		fgets(devices[oldCount + i].name, MAX_NAME_LENGTH, stdin);
		// 去除换行符
		devices[oldCount + i].name[strcspn(devices[oldCount + i].name, "\n")] = 0;
		
		printf("电线类型 (1-照明线路, 2-普通插座, 3-厨房卫生间, 4-空调线路): ");
		int wireType;
		if (scanf("%d", &wireType) != 1 || wireType < 1 || wireType > 4)
		{
			printf("输入无效，请输入1-4之间的电线类型编号!\n");
			i--; // 重新输入该设备
			while (getchar() != '\n'); // 清空输入缓冲区
			continue;
		}
		devices[oldCount + i].wireType = (WireType)wireType;
		newTypeCounts[wireType]++;
		while (getchar() != '\n'); // 清空输入缓冲区
	}
	
	// 计算每种类型的新顶点数量（+1 是为了包含电源结点）
	for (int type = 1; type <= 4; type++)
	{
		newTypeCounts[type] = oldTypeCounts[type] + newTypeCounts[type] + 1;
	}
	
	// 调整每种类型的图的大小
	for (int type = 1; type <= 4; type++)
	{
		if (newTypeCounts[type] > 1)   // 至少有一个设备和电源结点
		{
			if (graphs[type] == NULL)
			{
				graphs[type] = createGraph(newTypeCounts[type]);
			}
			else
			{
				graphs[type] = resizeGraph(graphs[type], newTypeCounts[type]);
			}
		}
	}
	
	// 重新分配图中的索引（电源结点为0，设备从1开始）
	int typeIndices[5] = {0};
	for (int i = 0; i < oldCount; i++)
	{
		WireType wireType = devices[i].wireType;
		devices[i].graphIndex = typeIndices[wireType] + 1;
		typeIndices[wireType]++;
	}
	
	for (int i = oldCount; i < newCount; i++)
	{
		WireType wireType = devices[i].wireType;
		devices[i].graphIndex = typeIndices[wireType] + 1;
		typeIndices[wireType]++;
	}
	
	// 更新设备数量
	*deviceCount = newCount;
	
	printf("成功添加 %d 个设备!\n", co87unt);
}

// 添加/修改边（包括电源连接）
void addEdges(Device *devices, int deviceCou87nt, Graph **graphs)
{
	if (deviceCou87nt == 0)
	{
		printf("错误: 无设备信息!\n");
		return;
	}
	
	printf("------------------------    添加/修改边    -----------------------------\n");
	printf("设备编号说明:\n");
	printf("0: 电源结点\n");
	for (int i87 = 0; i87 < deviceCou87nt; i87++)
	{
		printf("%d: %s (%s)\n", i87 + 1, devices[i87].name, getWireTypeName(devices[i87].wireType));
	}
	
	// 循环添加边
	while (1)
	{
		printf("\n输入边的信息 (格式: 设备1编号 设备2编号 长度, 输入0 0 0退出): ");
		int src, dest, weight;
		if (scanf("%d %d %d", &src, &dest, &weight) != 3)
		{
			printf("输入无效，请输入有效的格式!\n");
			while (getchar() != '\n'); // 清空输入缓冲区
			continue;
		}
		while (getchar() != '\n'); // 清空输入缓冲区
		
		if (src == 0 && dest == 0 && weight == 0)
		{
			break;
		}
		
		// 检查输入的有效性
		if ((src < 0 || src > deviceCou87nt) || (dest < 0 || dest > deviceCou87nt) || weight <= 0)
		{
			printf("输入无效，请输入有效的设备编号和正的长度!\n");
			continue;
		}
		
		// 禁止自己连接自己
		if (src == dest)
		{
			printf("错误: 设备不能自己连接自己!\n");
			continue;
		}
		
		// 获取设备类型
		WireType wireType;
		if (src == 0) {
			if (dest == 0) continue; // 已在前面检查
			wireType = devices[dest - 1].wireType;
		} else {
			wireType = devices[src - 1].wireType;
		}
		
		// 检查两个设备是否属于同一类型（除了电源连接）
		if (src != 0 && dest != 0 && devices[src - 1].wireType != devices[dest - 1].wireType)
		{
			printf("错误: 两个设备必须属于同一电线类型!\n");
			continue;
		}
		
		// 获取设备在对应图中的索引
		int srcIndex = (src == 0) ? 0 : devices[src - 1].graphIndex;
		int destIndex = (dest == 0) ? 0 : devices[dest - 1].graphIndex;
		
		// 添加边到对应图中
		addEdge(graphs[wireType], srcIndex, destIndex, weight);
		
		// 显示添加的边信息
		if (src == 0) {
			printf("添加电源连接: 电源 - %s (长度: %d)\n",
				devices[dest - 1].name, weight);
		} else if (dest == 0) {
			printf("添加电源连接: %s - 电源 (长度: %d)\n",
				devices[src - 1].name, weight);
		} else {
			printf("添加设备连接: %s - %s (长度: %d)\n",
				devices[src - 1].name, devices[dest - 1].name, weight);
		}
	}
	
	printf("边添加完成!\n");
}

int main()
{
	Device devices[MAX_VERTICES];
	int deviceCount = 0;
	Graph *graphs[5] = {NULL}; // 每种类型对应一个图，索引1-4对应四种电线类型
	int graphsInitialized = 0; // 标记图是否已经初始化
	
	while (1)
	{
		printf("----------------------------------------------------------------------------\n");
		printf("---------------------      《 家庭布线系统 》       ------------------------\n");
		printf("---------------------  1. 输入初始设备信息          ------------------------\n");
		printf("---------------------  2. 添加新设备信息            ------------------------\n");
		printf("---------------------  3. 添加/修改边               ------------------------\n");
		printf("---------------------  4. 计算最小布线长度          ------------------------\n");
		printf("---------------------  5. 显示所有设备              ------------------------\n");
		printf("---------------------  6. 显示所有边的权值          ------------------------\n");
		printf("---------------------  7. 退出                      ------------------------\n");
		printf("----------------------------------------------------------------------------\n");
		printf("请选择操作:> ");
		
		int choice;
		if (scanf("%d", &choice) != 1)
		{
			printf("输入无效，请输入有效的操作选择!\n");
			while (getchar() != '\n'); // 清空输入缓冲区
			continue;
		}
		while (getchar() != '\n'); // 清空输入缓冲区
		
		switch (choice)
		{
			case 1:   // 输入设备
			{
				printf("----------------------------    输入设备    --------------------------------\n");
				// 检查是否已有数据
				if (deviceCount > 0)
				{
					printf("错误: 已有设备数据，选择此操作将清除所有数据，是否继续? (y/n): ");
					char confirm;
					scanf(" %c", &confirm);
					while (getchar() != '\n'); // 清空输入缓冲区
					
					if (confirm != 'y' && confirm != 'Y')
					{
						printf("操作已取消!\n");
						break;
					}
					
					// 重置设备数量
					deviceCount = 0;
				}
				
				// 输入设备数量
				printf("输入设备数量 (最多%d个): ", MAX_VERTICES);
				int count = 0;
				if (scanf("%d", &count) != 1 || count <= 0 || deviceCount + count > MAX_VERTICES)
				{
					printf("输入无效，请输入有效的设备数量!\n");
					while (getchar() != '\n'); // 清空输入缓冲区
					break;
				}
				while (getchar() != '\n'); // 清空输入缓冲区
				
				for (int i = 0; i < count; i++)
				{
					printf("\n设备 %d:\n", deviceCount + 1);
					printf("名称: ");
					fgets(devices[deviceCount].name, MAX_NAME_LENGTH, stdin);
					// 去除换行符
					devices[deviceCount].name[strcspn(devices[deviceCount].name, "\n")] = 0;
					
					printf("电线类型 (1-照明线路, 2-普通插座, 3-厨房卫生间, 4-空调线路): ");
					int wireType;
					if (scanf("%d", &wireType) != 1 || wireType < 1 || wireType > 4)
					{
						printf("输入无效，请输入1-4之间的电线类型编号!\n");
						i--; // 重新输入该设备
						while (getchar() != '\n'); // 清空输入缓冲区
						continue;
					}
					devices[deviceCount].wireType = (WireType)wireType;
					while (getchar() != '\n'); // 清空输入缓冲区
					
					deviceCount++;
				}
				
				// 初始化图结构
				initializeGraphs(devices, deviceCount, graphs);
				graphsInitialized = 1;
				
				printf("设备输入完成! 请添加设备之间的连接或电源连接。\n");
				break;
			}
			
			case 2:   // 添加新设备信息
			{
				if (deviceCount >= MAX_VERTICES)
				{
					printf("错误: 设备数量已达到最大值(%d)!\n", MAX_VERTICES);
					break;
				}
				printf("------------------------    添加新设备信息    -----------------------------\n");
				displayDevices(devices, deviceCount);
				
				// 计算剩余可用空间
				int available = MAX_VERTICES - deviceCount;
				printf("\n当前有 %d 个设备，还可添加 %d 个设备\n", deviceCount, available);
				
				// 输入要添加的设备数量
				printf("输入要添加的设备数量: ");
				int count;
				if (scanf("%d", &count) != 1 || count <= 0 || count > available)
				{
					printf("输入无效，请输入有效的设备数量!\n");
					while (getchar() != '\n'); // 清空输入缓冲区
					break;
				}
				while (getchar() != '\n'); // 清空输入缓冲区
				
				// 添加设备并更新图结构
				addDevices(devices, &deviceCount, count, graphs);
				printf("添加新设备后，请添加设备之间的连接或电源连接!\n");
				break;
			}
			
			case 3:   // 添加/修改边
			{
				if (deviceCount == 0)
				{
					printf("错误: 无设备信息!\n");
					break;
				}
				
				// 如果图未初始化，先初始化图
				if (!graphsInitialized)
				{
					initializeGraphs(devices, deviceCount, graphs);
					graphsInitialized = 1;
				}
				
				// 调用合并后的边添加函数
				addEdges(devices, deviceCount, graphs);
				break;
			}
			
			case 4:   // 计算最小布线长度
			{
				if (deviceCount == 0)
				{
					printf("错误: 无设备信息!\n");
					break;
				}
				
				if (!graphsInitialized)
				{
					printf("错误: 无连接信息!\n");
					break;
				}
				printf("-----------------------    计算最小布线长度   -----------------------------\n");
				
				int totalLength = 0;
				
				// 对每种类型的图计算最小生成树
				for (int type = 1; type <= 4; type++)
				{
					if (graphs[type] != NULL && graphs[type]->V > 1)
					{
						int length = primMST(graphs[type]);
						totalLength += length;
						if (length >= INF)
						{
							printf("%s 存在设备未连接到图中\n", getWireTypeName((WireType)type));
						}
						else
						{
							printf("%s 需要布线长度: %d\n", getWireTypeName((WireType)type), length);
						}
					}
				}
				if (totalLength >= INF)
				{
					;
				}
				else
				{
					printf("总最小布线长度: %d\n", totalLength);
				}
				break;
			}
			
			case 5:   // 显示所有设备
			{
				displayDevices(devices, deviceCount);
				break;
			}
			
			case 6:   // 显示所有边的权值
			{
				if (deviceCount == 0)
				{
					printf("错误: 无设备信息!\n");
					break;
				}
				
				if (!graphsInitialized)
				{
					printf("错误: 无连接信息!\n");
					break;
				}
				
				displayEdges(devices, deviceCount, graphs);
				break;
			}
			
			case 7:   // 退出
			{
				// 释放内存
				for (int type = 1; type <= 4; type++)
				{
					freeGraph(graphs[type]);
				}
				
				printf("感谢使用家庭布线系统，再见!\n");
				return 0;
			}
			
		default:
			printf("无效的选择，请重新输入!\n");
		}
	}
	
	return 0;
}
